//
//  answer.cpp
//  JZ39 数组中出现次数超过一半的数字
//
//  Created by Yan Zihao on 2024/10/14.
//

/*
*思路：
* 1. 数组排序后，如果符合条件的数存在，则一定是数组中间那个数
  （比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等）
* 2. 查找满足条件的数 count > len/2，则出现次数大于一半
*/
class Solution
{
public:
  int MoreThanHalfNum_Solution(vector<int> numbers)
  {
    if(numbers.empty())
      return 0;
     
    sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数
    int middle = numbers[numbers.size()/2];
     
    int count=0; // 出现次数
    for(int i=0;i<numbers.size();++i)
    {
      if(numbers[i]==middle)
        ++count;
    }
     
    //返回符合条件的数
    return (count>numbers.size()/2) ? middle : 0;
  }
};
